package com.xy6.algo.search;

import java.util.Arrays;

/**
 * 哈希查找
 * <p>时间复杂度：O(1)
 * <p>适用于元素不重复的集合
 * 
 * <pre>
 * 根据集合元素大小，找到一个合适的素数，作为hash表初始化的长度；
 * 初始化hash表，默认值为0；
 * 构造一个hash函数（如除模取余m%n），用于计算元素在hash表中的索引key；
 * 遍历集合元素，取第1个元素，调用hash函数，得到一个key值，将元素保存到hash表索引为key的位置；
 * 保存前key%素数，避免数组越界；
 * 保存前判断索引为key的位置是否已有元素，若有，则key++，将元素保存到下一个索引位置；
 * 取第2个元素，重复上述步骤；
 * 直至遍历完集合所有元素，完成hash表构造过程；
 * 给定一个待查找的元素，根据hash函数找到元素的在hash表中的索引key，找到元素；
 * </pre>
 * 
 * @author zhang
 * @since 2017-08-15
 */
public class SearchHash {

	public static void main(String[] args) {
//		testSequential();
		testLink();
	}
	
	/**
	 * 线性探测法
	 */
	public static void testSequential(){
		// 除模取余法
		int hashLength = 13;
		
		int[] array = {13, 29, 27, 28, 26, 30, 38};
		
		int[] hash = new int[hashLength];
		
		// 创建hash
		for (int i = 0; i < array.length; i++) {
			insertHash(hash, hashLength, array[i]);
			System.out.println(Arrays.toString(hash));
		}
		
		int result = searchHash(hash, hashLength, 20);
		
		if(result != -1){
			System.out.println("元素在数组中索引为：" + result);
		} else {
			System.out.println("元素在数组中不存在");
		}
	}
	
	/**
	 * 数据插入hash表
	 * 
	 * @param hash
	 * @param hashLength
	 * @param data
	 */
	public static void insertHash(int[] hash, int hashLength, int data){
		// hash函数
		int hashAddress = data % hashLength;
		
		// 如果key值存在，则说明已经被被人占用，此时需解决冲突
		while(hash[hashAddress] != 0){
			// 用开放寻址法查找
			hashAddress = (++hashAddress) % hashLength;
		}
		
		// 将data存入字典
		hash[hashAddress] = data;
	}
	
	/**
	 * hash表检索数据
	 * 
	 * @param hash
	 * @param hashLength
	 * @param key
	 * @return
	 */
	public static int searchHash(int[] hash, int hashLength, int key){
		int hashAddress = key % hashLength;
		
		// 指定hashAddress对应值存在，但不是关键字，则使用开放寻址法查找
		while(hash[hashAddress] != 0 && hash[hashAddress] != key){
			hashAddress = (++hashAddress) % hashLength;
		}
		
		// 查找到了开放单元，表示查找失败
		if(hash[hashAddress] == 0){
			return - 1;
		}
		
		return hashAddress;
	}
	
	/**
	 * 数据插入hash表
	 * 
	 * @param hash
	 * @param hashLength
	 * @param data
	 */
	public static void insertHash2(SeparateChainingHashST[] hash, int hashLength, int data, int index){
		// hash函数
		int hashAddress = data % hashLength;
		
		// 如果key值存在，则说明已经被被人占用，此时需解决冲突
		if(hash[hashAddress] != null){
			// 用分链法存
			SeparateChainingHashST elem = hash[hashAddress];
			while(elem.getNext() != null){
				elem = elem.getNext();
			}
			elem.setNext(new SeparateChainingHashST(index, data));
		} else {
			hash[hashAddress] = new SeparateChainingHashST(index, data);
		}
	}
	
	/**
	 * hash表检索数据
	 * 
	 * @param hash
	 * @param hashLength
	 * @param key
	 * @return
	 */
	public static int searchHash2(SeparateChainingHashST[] hash, int hashLength, int key){
		int hashAddress = key % hashLength;
		
		if(hash[hashAddress] == null){
			return -1;
		}
		
		// 指定hashAddress对应值存在，遍历该位置上的链表
		SeparateChainingHashST elem = hash[hashAddress];
		while(elem != null && elem.getValue() != key){
			elem = elem.getNext();
		}
		if(elem == null){
			return -1;
		}
		return elem.getKey();
	}
	
	/**
	 * 拉链法
	 */
	public static void testLink(){
		// 除模取余法
		int hashLength = 13;
		
		int[] array = {13, 29, 27, 28, 26, 30, 38};
		
		SeparateChainingHashST[] hash = new SeparateChainingHashST[hashLength];
		
		// 创建hash
		for (int i = 0; i < array.length; i++) {
			insertHash2(hash, hashLength, array[i], i);
			System.out.println(Arrays.toString(hash));
		}
		
		int result = searchHash2(hash, hashLength, 30);
		
		if(result != -1){
			System.out.println("元素在数组中索引为：" + result);
		} else {
			System.out.println("元素在数组中不存在");
		}
	}
	
}
